package s12_经典算法.a0_回溯算法.s10_图;

import java.util.*;

/**
 * Created by 西瓜瓜
 * Date :2022/2/26
 * Description :
 * Version :1.0
 *
 * 图
 *
 * 深度优先遍历思想：
 * 1. 从初始访问节点出发，初始访问节点可能有多个邻接节点，深度优先遍历的策略就是首先访问第一个邻接节点，然后再以这个被访问的邻接节点作为初始节点，访问他的第一个邻接节点，可以这样理解：每次都在访问完当前节点后首先访问当前节点的第一个邻接节点
 * 2. 优先纵向挖掘深入
 * 3. 深度优先遍历是一个递归的过程
 * 算法步骤：
 * 1. 访问初始节点v,并标记节点v为已访问
 * 2. 查找节点v的第一个邻接节点w
 * 3. 若w存在，则继续执行4，如果w不存在，则回到第1步，将从v的下一个节点继续
 * 4. 若w未被访问，对w进行深度优先遍历（即把w当做另一个v，然后进行步骤123）
 * 5. 若w已被访问，查找节点v的w邻接节点的下一个邻接节点，转到步骤3
 *
 *
 * 广度优先遍历思想：
 * 类似于分层搜索的过程，广度优先遍历需要使用一个队列以保持访问过的节点的顺序，以便按照这个顺序来访问这些节点的邻接节点
 * 算法步骤：
 * 1. 访问初始节点v并标记节点v为已访问
 * 2. 节点v如队列
 * 3. 当队列非空时，继续执行，否则算法结束
 * 4. 出队列，取得队列头结点u
 * 5. 查找节点u的第一个邻接节点w
 * 6. 若节点u的邻接节点w不存在，则转到步骤3，否则循环执行一下3个步骤
 * 6.1 若节点w尚未被访问，则访问节点w并标记为已访问
 * 6.2 节点w入队列
 * 6.3 查找节点u的w邻接节点后的下一个邻接节点w，转到步骤6
 *
 */
public class Graph {

    /** 存储顶点的集合 */
    private List<String> vertexList;

    /** 存储图对应的邻接矩阵 */
    private int[][] edges;

    /** 表示边的数目 */
    private int numOfEdges;

    /** 记录某个节点是否被访问 */
    private boolean[] isVisited;

    public Graph(int n) {
        // 初始化矩阵和vertexList
        this.edges = new int[n][n];
        this.vertexList = new ArrayList<>(n);
        this.numOfEdges = 0;
        this.isVisited = new boolean[n];
    }

    /**
     * 添加顶点
     * @param vertex
     */
    public void insertVertex(String vertex) {
        vertexList.add(vertex);
    }

    /**
     * 添加边
     * @param v1 第一点的下标
     * @param v2 第二点的下标
     * @param weight 点的关联值
     */
    public void insertEdge(int v1, int v2, int weight) {
        edges[v1][v2] = weight;
        edges[v2][v1] = weight;
        numOfEdges++;
    }

    /**
     * 节点的个数
     * @return
     */
    public int getNumOfVertex() {
        return vertexList.size();
    }

    /**
     * 节点的下标
     * @return
     */
    public int getEdgeIndex(String vertexValue) {
        return vertexList.indexOf(vertexValue);
    }

    /**
     * 边的个数
     * @return
     */
    public int getNumOfEdges() {
        return numOfEdges;
    }

    /**
     * 返回节点下标对应的数据
     * @param i
     * @return
     */
    public String getValueByIndex(int i) {
        return vertexList.get(i);
    }

    /**
     * 返回权值
     * @param v1
     * @param v2
     * @return
     */
    public int getWeight(int v1, int v2) {
        return edges[v1][v2];
    }

    /**
     * 显示矩阵
     */
    public void showGraph() {
        for (int[] edge : edges) {
            System.out.println(Arrays.toString(edge));
        }
    }

    /**
     * 得到第一个邻接节点的下标w
     * @param index
     * @return
     */
    public int getFirstNeighbor(int index) {
        for (int i = 0; i < vertexList.size(); i++) {
            if(edges[index][i] > 0) {
                return i;
            }
        }
        return -1;
    }

    /**
     * 根据前一个邻接节点的下标来获取下一个邻接节点
     * @param v1
     * @param v2
     * @return
     */
    public int getNextNeighbor(int v1, int v2) {
        for(int i=v2+1; i<vertexList.size(); i++) {
            if(edges[v1][i] > 0) {
                return i;
            }
        }
        return -1;
    }

    /**
     * 深度遍历
     * @param isVisited
     * @param i
     */
    private void dfs(boolean[] isVisited, int i) {
        System.out.print(getValueByIndex(i) + "->");
        // 将节点设置为已访问
        isVisited[i] = true;

        int w = getFirstNeighbor(i);
        while(w != -1) {
            if(!isVisited[w]) {
                dfs(isVisited, w);
            }
            // 如果w节点已经被访问过
            w = getNextNeighbor(i, w);
        }
    }

    /**
     * 深度优先遍历重载，
     */
    public void dfs() {
        // 遍历所有节点进行dfs
        for(int i=0; i<getNumOfVertex(); i++) {
            if(!isVisited[i]) {
                dfs(isVisited, i);
            }
        }
    }

    /**
     * 对1个节点进行广度优先
     * @param isVisited
     * @param i
     */
    private void bfs(boolean[] isVisited, int i) {
        // 表示队列头结点对应的下标
        int u;
        // 邻接节点w
        int w;
        // 记录节点访问的顺序
        Queue<Integer> queue = new LinkedList<>();
        // 访问节点，
        System.out.print(getValueByIndex(i) + "->");
        // 将节点设置为已访问
        isVisited[i] = true;

        // 将节点加入队列
        queue.add(i);

        while(!queue.isEmpty()) {
            // 取出队列头结点下标
            u = queue.poll();
            w = getFirstNeighbor(u);
            while(w != -1) {
                if(!isVisited[w]) {
                    System.out.print(getValueByIndex(w) + "->");
                    // 将节点设置为已访问
                    isVisited[w] = true;
                    // 将节点加入队列
                    queue.add(w);
                }
                // 以u为前驱，找w后面的下一个邻接节点
                w = getNextNeighbor(u, w);
            }
        }
    }

    /**
     * 广度优先
     */
    public void bfs() {
        // 遍历所有节点进行bfs
        for(int i=0; i<getNumOfVertex(); i++) {
            if(!isVisited[i]) {
                bfs(isVisited, i);
            }
        }
    }
    
    
    
    
    public static void main(String[] args) {
        // 创建5个节点的图
        Graph graph = new Graph(5);

        String[] vertexValue = {"A", "B", "C", "D", "E"};

        // 添加顶点
        for (String value : vertexValue) {
            graph.insertVertex(value);
        }
        // 添加边
        // A-B A-C B-C B-D B-E
        graph.insertEdge(graph.getEdgeIndex("A"), graph.getEdgeIndex("B"), 1);
        graph.insertEdge(graph.getEdgeIndex("A"), graph.getEdgeIndex("C"), 1);
        graph.insertEdge(graph.getEdgeIndex("B"), graph.getEdgeIndex("C"), 1);
        graph.insertEdge(graph.getEdgeIndex("B"), graph.getEdgeIndex("D"), 1);
        graph.insertEdge(graph.getEdgeIndex("B"), graph.getEdgeIndex("E"), 1);

        graph.showGraph();

        // 深度优先遍历
//        graph.dfs();
        // 广度优先遍历
        graph.bfs();


    }

}
